论文笔记[1]——随机分配问题的PS算法和依次有效性

发表于 | 分类于

文章: Bogomolnaia A, Moulin H. A New Solution to the Random Assignment Problem[J]. Journal of Economic Theory, 2001, 100(2):295-328.

  • \(n\) 个物品被分配给 \(n\) 个人的问题, 称为分配问题. 生活中此类问题常采取抽签方式解决. 在此基础上可归纳出一种RP算法.
  • 文章对已有的RP算法进行了讨论, 并提出了一种新的分配方法, PS算法.

分配问题

分配问题: \(n\) 个物品被分配给 \(n\) 个人的问题, 称为分配问题.

分配中, 每个人都对这 \(n\) 个东西有一个偏好顺序. 此处假定每个人的偏好关系是严格的, 即每个人对任何两个物品都有一个严格的排序.

随机优先(RP)算法

RP \(n\) 个人随机选定一个选择的顺序, 按照顺序在 \(n\) 个物品中选择.

很容易发现RP算法有以下两点好处:

  • RP算法看起来是比较公平的;
  • RP算法是防策略(Strategyproofness)的, 即大家都会选择说真话.

但用VNM效用函数去分析时, RP算法存在缺陷.

VNM效用 设某人得到物品 \(x_i\) 的概率为 \(P_i\), 在得到 \(x_i\) 时的效用为 \(u(x_i)\), 则其VNM效用为 \[U(X)=\sum_i P_i u(x_i)\]

分析可知:

  • 在使VNM效用最大化的意义下, RP算法并不总是最优的.

但RP算法具有如下两个优势:

  1. 事后有效 (ex post efficient): 每次分配确定的方案都是Pareto最优的. 即增大某人利益的同时一定会损害其他人的利益.
  2. 算法简单: RP算法在分配时, 每一轮只需要考虑一个人的偏好.

概率序列(PS)算法

考虑一个例子:

  • 参与者1, 2: \(a\succ b\succ c\succ d\);
  • 参与者3, 4: \(b\succ a\succ d\succ c\).

则RP算法的概率矩阵为 \(A\)(每行代表一个人, 每列代表一样物品). 然而考虑 \(B\) 可知, 无论效用函数的形式如何, 概率矩阵 \(B\) 都比RP算法得到的结果要好. \[A=\begin{bmatrix}\frac{5}{12}&\frac{1}{12}&\frac{5}{12}&\frac{1}{12}\\ \frac{5}{12}&\frac{1}{12}&\frac{5}{12}&\frac{1}{12}\\ \frac{1}{12}&\frac{5}{12}&\frac{1}{12}&\frac{5}{12}\\ \frac{1}{12}&\frac{5}{12}&\frac{1}{12}&\frac{5}{12}\\ \end{bmatrix},~B=\begin{bmatrix}\frac{1}{2}&0&\frac{1}{2}&0\\ \frac{1}{2}&0&\frac{1}{2}&0\\ 0&\frac{1}{2}&0&\frac{1}{2}\\ 0&\frac{1}{2}&0&\frac{1}{2}\\ \end{bmatrix}\]

\(B\) 矩阵的获取可从如下角度考虑:

在分配中, 将每个物品都视为一种食物, 偏好关系表示对食物的喜好. 所有的人同时开始以相同速率(不妨设为1)吃东西. 每个人都会优先吃自己最喜欢的食物. 当一样食物被吃完时, 该食物即被分配给吃该食物量最多的人.

PS算法的有效性

形式化定义

设参与者的集合为 \(N\), 物品集合为 \(A\), 集合大小为 \(\vert N\vert=\vert A\vert=n\).

确定性分配与随机性分配

  • Deterministic Assignment: \(N\to A\) 的一一映射, 可用 \(n\times n\) 的置换矩阵表示. 记这样的分配构成的集合为 \(\mathscr{D}\);
  • Random Allocation: \(A\) 上的概率分布, 可用各个分量和为1的 \(n\) 维向量表示. 记这样的分配构成的集合为 \(\mathscr{L}(A)\);
  • Random Assignment: \(\mathscr{D}\) 上的概率分布, 可用一个 \(n\times n\) 的双随机矩阵(Bistochastic)表示. 即: \[P=[p_{ia}]_{i\in N,a\in A}~~其中~~P=\sum\limits_{\Pi\in D}\lambda_\Pi\cdot\Pi,~\lambda_\Pi\geqslant 0,~\sum_\Pi\lambda_\Pi=1\]矩阵的第 \(i\) 行 \(P_i\) 对应第 \(i\) 个人的Random Allocation. \(p_{ia}\) 表示 \(i\) 得到物品 \(a\) 的概率. 双随机矩阵构成的集合记为 \(\mathscr{R}\).

双随机矩阵可定义为: 每行每列和都为 \(1\) 的矩阵. 如此可得到以下结论:
1. 第 \(i\) 行可视为编号为 \(i\) 的人对于 \(A\) 中物品的效用分布;
2. 第 \(j\) 列可视为 \(N\) 中的每个人得到编号为 \(j\) 的物品的可能性.

效用函数与偏好关系

  • Preference: 每个参与者对物品都存在一个严格的偏好关系, 即对应于 \(A\) 上的一个序关系 \(\succ_i\). 记所有这样的偏好关系构成的集合为 \(\mathscr{A}\);
  • VNM Utility: 每个参与者拿到 \(A\) 中的一件物品时, 产生的效用可视作 \(A\to\mathbb{R}\) 的函数, 记作 \(u_i\). 效用函数实际上是偏好程度的量化.

称效用函数 \(u_i\) 和偏好关系 \(\succ_i\) 是相容(compatible)的, 如果 \[u_i(a)>u_i(b)\iff a\succ_ib,~\forall a,b\in A.\]

确定性分配的有效性

  • Priority Assignment: 考虑偏好关系 \(\succ=\{\succ_i\}_{i\in N}\), 设 \(\sigma\) 是 \(N\) 的一个排列, 则按 \(\sigma\) 的顺序进行分配即可得到一个分配方案, 即Priority Assignment. 记作 \(Prio(\sigma,\succ)\);
以下记 \(N\) 的所有排列构成的集合为 \(\theta\).

一个Deterministic Assignment \(\Pi\) 称为有效的, 如果\[\exists\sigma\in\theta,~ \text{s.t.}~ \Pi=Prio(\sigma,\succ).\]

关于确定性分配的有效性, 很容易得到下述引理:

LEMMA 1. 给定偏好关系 \(\succ\in\mathscr{A}^N\) 和确定性分配 \(\Pi\), 则下列命题等价:
1. \(\Pi\) 在 \(\mathscr{D}\) 中是Pareto最优的;
2. \(\forall\) 效用函数组 \(u=\{u_i\}\), \(\Pi\) 在 \(\mathscr{R}\) 中对 \(u\) 是Pareto最优的;
3. \(\exists\sigma\in\theta\), s.t. \(\Pi=Prio(\sigma,\succ)\).

随机性分配的有效性

首先定义事前评估有效(ex ante efficient)和事后评估有效(ex post efficient):

Definition 1. 给定随机性分配 \(P\in\mathscr{R}\), 偏好关系组 \(\succ\in\mathscr{A}^N\) 和VNM效用函数组 \(u\), 则有定义:
1. \(P\) 对 \(u\) 是事前评估有效的, iff \(P\) 在 \(\mathscr{R}\) 中对 \(u\) 是Pareto最优的;
2. \(P\) 对 \(\succ\) 是事后评估有效的, iff \(P\) 可被表示为有效的deterministic assignments上的概率分布, 即 \(P\) 满足\[P=\sum_{\sigma\in\theta}\mu_\sigma\cdot Prio(\sigma,\succ),~~~\mu_\sigma\geqslant 0,~\sum_{\sigma\in\theta}\mu_\sigma=1.\]

根据上式可知, 所有事后评估有效的分配方案存在一个中心点(natural central point). 这个中心点就是随机优先分配(Random Priority), 即 \[RP(\succ)=\frac{1}{n!}\sum_{\sigma\in\theta}Prio(\sigma,\succ).\]

随机占优关系

考虑 \(A\) 上的序关系 \(\succ_i\), 假设 \(a_1\succ_ia_2\succ_i\cdots\succ_ia_n\).

可如下定义 \(\mathscr{L}(A)\) 上的一个偏序关系 \(sd(\succ_i)\): \[P_i~sd(\succ_i)~Q_i\iff\left\{\sum\limits_{k=1}^tp_{ia_k}\geqslant\sum\limits_{k=1}^tq_{ia_k},~\forall t=1,\cdots,n\right\},~P_i,Q_i\in\mathscr{L}(A).\] 该偏序关系称作随机占优(stochastic dominance).

关于随机占优, 容易得到如下结论:

\(\forall P_i,Q_i\in\mathscr{L}(A)\), \(P_i~sd(\succ_i)~Q_i\) iff \(\forall\) 与 \(\succ_i\) 相容的 \(u_i\), 总有 \[u_i\cdot P_i\geqslant u_i\cdot Q_i.\]

进一步可以将随机占优关系推到 \(\mathscr{R}\) 上:

DEFINITION 2. 给定偏好 \(\succ\), \(P,Q\in\mathscr{R}\), 称 \(Q\) 随机占优于 \(P\)(\(P\) is stochastically dominated by \(Q\)), 如果 \[Q_i~sd(\succ_i)~P_i,~\forall i~且~Q\neq P\]

依次有效性

给定偏好关系 \(\succ\), 称 \(P\in\mathscr{R}\) 是依次有效的, 如果不存在 \(Q\in\mathscr{R}\), s.t. \(Q\) 随机占优于 \(P\).

依次有效性与事前/事后评估有如下关系:

LEMMA 2. 给定一个Random Assignment \(P\in\mathscr{R}\), 一个偏好关系 \(\succ\), 和一组与 \(\succ\) 相容的效用函数 \(u\), 则有:
1. 若 \(P\) 对 \(u\) 是事前评估有效的, 则 \(P\) 对 \(\succ\) 是依次有效的. (逆命题在 \(n=2\) 时成立, \(n\geqslant 3\) 时可能失效);
2. 若 \(P\) 对 \(\succ\) 是依次有效的, 则 \(P\) 对 \(\succ\) 是事后评估有效的. (逆命题在 \(n\leqslant 3\) 时成立, \(n\geqslant 4\) 时可能失效).

进食算法

在PS算法处已经实际上介绍了进食算法:

SIMULTANEOUS EATING ALGORITHM
　　给定偏好关系 \(\succ\) 和一组函数 \(\{\omega_i(t)\}_{i\in N}\), s.t. \(\omega_i(t)\geqslant 0\), 且 \(\int_0^1\omega_i(t){\rm d}t=1\), 表示进食的速度.
　　所有的人按照自己的偏好关系开始进食, 并且在每个时刻, 每个参与者都吃自己当前最想吃并且有剩余的物品.

进食算法的依次有效性

依次有效的条件

在 \(\mathscr{R}\) 上可如下定义一个二元关系 \(\tau\):

DEFINITION 2. 给定一个 Random Assignment \(P\in\mathscr{R}\) 和偏好关系 \(\succ\), 如下定义 \(\tau\): \[a\tau(P,\succ)b\iff \exists i\in N,~s.t.~a\succ_ib,~p_{ib}>0.\]

  • \(a\tau b\) 其实表示的是: 存在一个 \(i\), 比起 \(b\) 更喜欢 \(a\), 但有可能会得到 \(b\).

根据二元关系 \(\tau\) 可得到依次有效的等价条件:

LEMMA 3. 一个Random Assignment \(P\in\mathscr{R}\) 是依次有效的, iff \(\tau(P,\succ)\) 无环(acyclic).

其证明并不困难:

  • 充分性: 假设有一个环, 沿着环转一圈即可得到一个随机占优于 \(P\) 的Assignment.
  • 必要性: 假设存在 \(Q\) 随机占优于 \(P\), 则可直接得到一个 \(\tau\) 的环.

进食算法的依次有效性

进食算法是依次有效的.

其证明也很简单, 直接利用引理 1即可.

假设进食算法不是依次有效的, 则 \(\tau\) 存在环: \[a_0\tau a_1\tau\cdots \tau a_k\tau a_0.\] 于是按照算法, 有如下命题:

  • \(i_0\) 开始吃 \(a_1\) 的时候, \(a_0\) 已经被吃完, 故 \(a_0\) 比 \(a_1\) 更早被开始吃;
  • \(i_1\) 开始吃 \(a_2\) 的时候, \(a_1\) 已经被吃完, 故 \(a_1\) 比 \(a_2\) 更早被开始吃;
  • \(\cdots\cdots\)
  • \(i_k\) 开始吃 \(a_0\) 的时候, \(a_k\) 已经被吃完, 故 \(a_k\) 比 \(a_0\) 更早被开始吃.

这显然是一个矛盾.

进食算法的有效性由下列定理给出:

THEOREM 1. 给定偏好关系 \(\succ\in\mathscr{A}^N\), 对于任一组进食速率函数 \(\omega=\{\omega_i\}_{i\in N}\), Random Assignment \(P_\omega(\succ)\) 总是依次有效的.
　　反过来, 对于任一个对 \(\succ\) 依次有效的Random Assignment \(P\), 存在一组进食速率函数 \(\omega=\{\omega_i\}_{i\in N}\), s.t. \(P=P_\omega(\succ)\).

PS算法

至此我们可以严格地定义PS算法:

DEFINITION 4. 满足 \(\omega_i(t)\equiv 1,~\forall t\in[0,1],~\forall i\in N\) 的进食算法即为PS算法. 记作 \(PS(\succ)\).

PS算法有如下两条性质:

  1. PS算法是依次有效的, 由定理1即得;
  2. PS算法是匿名的, 即对于 \(n\) 个人的身份对称.

关于以上的(2), 有如下引理:

LEMMA 4. 给定一组进食速率函数 \(\omega=(\omega_1,\cdots,\omega_n)\), \(P\) 是由 \(\omega\) 生成的分配机制(mechanism). 则 \(P\) 是匿名的当且仅当 \(P\) 是PS算法.

RP算法与PS算法的比较

略去文中的例子, 直接不加证明地给出文中的结论:

无嫉妒性

无嫉妒性(envy-free)定义如下:

DEFINITION 4. 称Random Assignment \(P\in\mathscr{R}\) 是无嫉妒/弱无嫉妒(envy-free/weak envy-free)的, 当且仅当对 \(\forall i,j\in N\), 总有:
无嫉妒 \(P_i~sd(\succ_i)~P_j\)
弱无嫉妒 \(P_j~sd(\succ_i)~P_j\Rightarrow P_i=P_j\)

防策略性

防策略性(strategyproofness)定义如下:

DEFINITION 5. 称一个分配机制 \(P(\cdot)\) 是防策略/弱防策略(strategyproofness/weak strategyproofness)的, 当且仅当对 \(\forall i,j\in N\), 总有:
防策略 \(P_i(\succ)~sd(\succ_i)~P_i(\succ\vert^i\succ_i^*)\)
弱防策略 \(P_i(\succ\vert^i\succ_i^*)~sd(\succ_i)~P_i(\succ)\Rightarrow P_i(\succ)=P_i(\succ\vert^i\succ_i^*)\)

PS与RP的比较

对任意的偏好关系 \(\succ\in\mathscr{A}^N\), PS与RP的关系如下:
无嫉妒性 防策略性
RP 弱无嫉妒 防策略
PS 无嫉妒 弱防策略